package com.ywk.base.dataStructure.linkedlist;
//约瑟夫（环）出队问题
public class Josphu {

	public static void main(String[] args) {
		JosLinkedList jl=new JosLinkedList();
		jl.addJosphu(10);
		System.out.println("原单链表：");
		jl.showJos();
		System.out.println("出队顺序：");
		jl.teamOut(3);
		
	}

}



class JosLinkedList{
	private JosNode first=null;//辅助指针，始终指向第一个结点
	//根据nums值构建nums个结点的环形单链表
	public void addJosphu(int nums) {
		if(nums<1) {
			System.out.println("nums值不正确");
			return;
		}
		JosNode curr=null;//辅助指针，指向当前添加的结点
		for (int i = 1; i <= nums; i++) {
			JosNode n=new JosNode();
			n.setNo(i);
			if(i==1) {
				 first=n;
				 curr=n;
				 n.next=first;
			}else {
				curr.next=n;
				n.next=first;
				curr=n;//辅助指针后移
			}
		}
	}
	
	//根据count值出队，形成出队序列
	public void teamOut(int count) {
		JosNode p=first;
		int c=0;
		while(true) {
			c++;
			if(c==count-1) {//因为是单链表，要将一个结点从链表移除，必须将辅助指针指向这个待移除结点的前一个结点
				if(p.next==p) {//判断是否为最后出队的结点（必须放在前面）
					System.out.println(p.next.getNo());
					break;
				}
				System.out.println(p.next.getNo());
				p.next=p.next.next;
				c=0;
			} 
			p=p.next;
		}
	}
	
	public void showJos() {
		JosNode p=first;
		while(true) {
			System.out.println(p);
			if(p.next==first) {
				break;
			}
			p=p.next;
		}
	}
	
}



class JosNode{
	private int no;
	private String name;
	public JosNode next;
	
	public JosNode() {
		super();
	}

	public JosNode(int no, String name) {
		super();
		this.no = no;
		this.name = name;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	@Override
	public String toString() {
		return "Node [no=" + no + ", name=" + name + ", next=" + next.no + "]";
	}
	
	
}